def cmp(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return 1
        else:
            return -1
    for i in range(len(a)): #选择字典序小的
        if a[i] < b[i]:
            return 1 #字典序小的反而比较大，所以返回1
        elif a[i] > b[i]:
            return -1
    return 0


if __name__ == '__main__':
    words = []
    map1 = {}
    with open('words.txt', 'r') as f:
        lines = f.readlines()
        for line in lines:
            # word = list(line[0:-1])  #"tdasm\n" ,[t,d,a,s,m]
            # word = "".join(word)
            word = word[0:-1]
            words.append(word)
            if len(word) in map1:
                map1[len(word)].append(word)
            else:
                map1[len(word)] = [word]
    max_length = 0 #当前优美字符串的最大长度
    ans = '' #存储最长的优美字符串，如果有多个等长的，选择字典序最小的
    set1 = set() #存储优美字符串的集合
    for word in map1[1]: #遍历所有长度为1的字符串，它们必然是优美字符串
        set1.add(word)
        queue1 = [] #队列，基于队列做bfs
        if cmp(word, ans) == 1:
            max_length = 1
            ans = word
        queue1.append(word) # queue 原本的数据类型是字符串
        while len(queue1) > 0: #当队列非空
            tmp = list(queue1[0]) #拿队头元素，转列表
            del queue1[0] #出队列
            tmp.sort() #从小到大的排序
            tmp = ''.join(tmp) #转回字符串
            if len(tmp) + 1 not in map1: #不在数据集中
                continue #开始下一次搜索
            for next in map1[len(tmp) + 1]: #遍历所有可能的下个长度为当前长度+1的字符串
                pre = next[0:-1] #除了最后一位都要
                pre = list(pre)
                pre.sort() #从小到大排序
                pre = "".join(pre)
                if pre == tmp: #可以证明next也是优美字符串
                    if next not in set1: #避免重复计算
                        set1.add(next)
                    else:
                        continue #已经计算过了
                    if cmp(next, ans) == 1: #一定是符合要求的结果
                        max_length = len(next)
                        ans = next
                    queue1.append(next) #入队列，辅助下一次计算
    print(ans)
